1. Technical Field
The invention is directed to apparatus and methods for minimizing lock contention in a multiple run queue system.
2. Description of Related Art
Multiple processor systems are generally known in the art. In a multiple processor system, a process may be shared by a plurality of processors. The process is broken up into threads which may be executed concurrently. However, the threads must be queued for each of the processors of the multiple processor system before they may be executed by a processor.
One known technique for queuing threads to be dispatched by a processor in a multiple processor system is to maintain a single centralized queue, or “run queue.” As processors become available, they take the next thread in the queue and process it. The drawback to this approach is that the centralized queue becomes a bottleneck for the threads and processing time may be lost due to processors spinning on a run queue lock, i.e. becoming effectively idle, while waiting to take the next thread from the centralized queue.
Another known technique for queuing threads is to maintain separate queues for each processor. Thus, when a thread is created, it is assigned to a processor in some fashion. With such a technique, some processors may become overloaded while other processors are relatively idle. Furthermore, some low priority threads may become starved, i.e. are not provided with any processing time, because higher priority threads are added to the run queue of the processor for which the low priority threads are waiting.
U.S. patent application Ser. Nos. 09/506,230, 09/506,856, and 09/506,231 describe an apparatus that performs initial load balancing, idle load balancing, periodic load balancing and starvation load balancing to ensure that the workloads for the processors of the system are reasonably balanced. These prior apparatus use both per-processor run queues, called local run queues, and run queues served by multiple processors, called global run queues, to manage their threads. Initial load balancing deals with the assignment of a new thread to a global run queue or to one of the local run queues. Idle load balancing addresses how to shift threads from one local run queue to another when a processor is becoming idle. Periodic load balancing addresses how to shift threads from the heaviest loaded local run queue to the lightest loaded local run queue in order to maintain a load balance. Starvation load balancing addresses how to requeue threads that are being starved of processing time.
Using these load balancing schemes, there are two potential areas for excessive lock contention. One area is at the “front end” of the dispatcher, where the choice must be made either to dispatch a thread from a global run queue or to dispatch a thread from a processor's local run queue. The other area of lock contention is at the “back end” of the dispatcher, where neither the global nor local queues have work to be dispatched and lock contention is generated when idle load balancing tries to shift work between local run queues of the processors.
Thus, there is a need for new technology to provide apparatus and methods for minimizing lock contention in a multiple processor system.